#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
#include <vector>
#include <algorithm>    // std::sort
using namespace std;

// ---------------------------------
// QUESTOES (algoritmos principais)
// ---------------------------------
void Questao4(int N);
void Questao6(int N);
void Questao7(int N);
int  Questao9(vector<int>& v, int p, int r);
int  Questao10(vector<int>& v1, vector<int>& v2, int p1, int r1, int p2, int r2);
void Questao11(vector<int>& v, int n, int x);
int  Questao12(vector<int>& v, int p, int r);
void Questao14a(vector<int>& v, int n, int k);
void Questao14b(vector<int>& v, int n, int k1, int k2);
void Questao14bb(vector<int>& v, int n, int k);
int  Questao16(vector<int>& v, int N, double prob);
void Questao17(vector<double>& v, int N, int K, double relax);


// ----------------------
// algoritmos auxiliares
// ----------------------
void HeapSort(vector<int>& v, int p, int r);
void InsertionSort(vector<int>& v, int p, int r);
void CountingSort(vector<double>& A, int N, int K);
int Busca_Binaria(vector<int>& v, int elemento, int p, int r);
int Selecao(vector<int>& v, int p, int r, int k);
void imprimir_vetor(vector<auto>& v, int N, string filename);

int intQuestao4;



// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
	int i,N;
	vector<int> v, v1, v2;

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 4 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	ofstream arq;
	arq<<fixed;
	arq.open("saida_questao4.txt");
    arq<<"N\tT(N)\tN*log(N,10)\tN*log(N,6)\tN*log(N,5)"<<endl;

	cout<<endl;
	for (int i=10000; i<=3000000; i+=10000) {
	    intQuestao4 = 0;
	    Questao4(i);
	    arq<<i<<"\t"<<intQuestao4<<"\t"<<(int)(i*log(i)/log(10))<<"\t"<<(int)(i*log(i)/log(6))<<"\t"<<(int)(i*log(i)/log(5))<<"\t"<<endl;
	}
	arq.close();
	cout << "<Questao4> Ok: ver arquivo saida_questao4.txt" << endl;


	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 6 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao6(20); //par
	Questao6(21); //impar

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 7 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";

	Questao7(50);

	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 9 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	cout<<endl;
	N = 1001; //N=1000;
	for (i=0; i<N; i++) v.push_back(11 + i%2);
	int maj = Questao9(v,0,N-1);
	if (maj<0) cout<<"<Questao9> NAO tem majoritario"<<endl;
	else cout<<"<Questao9> Tem majoritario = "<<maj<<endl;
	v.clear();



	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 10 ---------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	cout<<endl;
	N = 16;
	for (i=0; i<N; i++) v1.push_back(1*i);
	for (i=0; i<N; i++) v2.push_back(2*i);
	//HeapSort(vetor10a,0,N-1); HeapSort(vetor10b,0,N-1);
	imprimir_vetor(v1, N, "entrada_questao10a.txt");
	imprimir_vetor(v2, N, "entrada_questao10b.txt");

	int med = Questao10(v1,v2,0,N-1,0,N-1);
	cout<<"<Questao10> Mediana de X1 e X2 ordenados: = "<<med<<endl;
	v1.clear(); v2.clear();



	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 11 ---------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	cout<<endl;
	N = 250000;
	for (i=0; i<N; i++) v.push_back(0);
	v[10000] = 4999;
	v[20000] = 5001;
	Questao11(v, N, 10000);
	Questao11(v, N, 10001);
	v.clear();


	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 12 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	cout<<endl;
	N = 1000;
	for (i=0; i<N; i++) if (i%2==0) v.push_back(i); else v.push_back(i-2);

	int inv = Questao12(v,0,N-1);
	cout<<"<Questao12> Numero de inversoes = "<<inv<<endl;
	v.clear();


	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 14 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	cout<<endl;
	int k = 16;
	N = 10;
	srand(time(NULL));
	for (i=0; i<k*N; i++) v.push_back(rand() % 100);
	for (i=0; i<k; i++) {
        sort(v.begin()+i*N, v.begin() + i*N + N);
	}
	imprimir_vetor(v, k*N, "entrada_questao14.txt");

	//Questao14a(vetor,N,k);
	//Questao14bb(v,N,k);
	Questao14b(v,N,1,k);
	imprimir_vetor(v, k*N, "saida_questao14.txt");
	cout << "<Questao14> Ok: ver arquivo saida_questao14.txt" << endl;
	v.clear();


	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 16 ---------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	cout<<endl;
	N = 1000; //N=1002;
	double prob = 1.0/3;
	for (i=0; i<N; i++) v.push_back(11 + i%3);
	int pop = Questao16(v, N, prob);
	if (pop<0) cout<<"<Questao16> NAO tem popular"<<endl;
	else cout<<"<Questao16> Tem popular = "<<pop<<endl;
	v.clear();


	cout<<"-------------------------------------------------------------\n";
	cout<<"---------------- QUESTAO 17 ----------------------------------\n";
	cout<<"-------------------------------------------------------------\n";
	cout<<endl;
	N = 1000;
	int K=100;
	vector<double> V;
	for (i=0; i<N; i++) V.push_back((double) K * rand()/RAND_MAX);
	double relax = 0.1; // A[i]<A[i+1]+relax //relax > 0
	Questao17(V, N, K, relax);
	imprimir_vetor(V, N, "saida_questao17.txt");
	cout<<"<Questao17> ver arquivo saida_questao17.txt"<<endl;
	V.clear();


	return 0;
}













// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 4 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Considere o algoritmo {\sc NumRecursivo}$(N)$ abaixo. Determine o valor retornado em notação assintótica.

void Questao4(int N) {
    if (N<=1) return;
    intQuestao4 += N;
    Questao4(N/5);
    Questao4(N/5);
    Questao4(N/6);
    Questao4(N/6);
    Questao4(N/6);
    Questao4(N/10);
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 6 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Considere vetores que satisfazem a propriedade: o subvetor dos índices ímpares está ordenado crescentemente e o dos índices pares está ordenado decrescentemente.
//Exemplo: A=[1 50 2 40 3 30 4 20 5 10]. Faça um algoritmo de tempo $O(\log n)$ que receba um vetor desse tipo e um inteiro $x$, e informe se $x$ está no vetor, retornando sua posição, se for o caso.

void trocar(int& x, int& y) {int z = x; x = y; y = z;}

int Questao6busca(vector<int>& v, int elemento, int N) {
    int p,q,r;

    // Busca Binária nas posicoes impares (ordenado crescentemente)
    p=1; r=(N+1)/2;
    while (p<=r) {
        int q = (p+r)/2;
        if (v[2*q-1]< elemento) p = q+1; else
        if (v[2*q-1]> elemento) r = q-1; else
        if (v[2*q-1]==elemento) return 2*q-1;
    }
    // Busca Binária (invertida) nas posicoes pares (ordenado decrescentemente)
    p=1; r=N/2;
    while (p<=r) {
        int q = (p+r)/2;
        if (v[2*q]> elemento) p = q+1; else
        if (v[2*q]< elemento) r = q-1; else
        if (v[2*q]==elemento) return 2*q;
    }
    return -1;
}

void Questao6(int N) {
    vector<int> v(N+1,0);
	for (int i=1; i<=N; i+=2) v[i] = i;
	for (int i=2; i<=N; i+=2) v[i] = N-i+2 -N%2;
	cout<<"Vetor[1..."<<N<<"] = (";
	for (int i=1; i<=N; i++) cout<<v[i]<<" ";
	cout<<")\n\n";

	int elemento = 7;
	int q = Questao6busca(v, elemento, N);
	if (q<0) cout<<"Elemento "<<elemento<<" nao encontrado\n";
	else cout<<"Elemento "<<elemento<<" encontrado na posicao "<<q<<"\n";

	elemento = 14;
	q = Questao6busca(v, elemento, N);
	if (q<0) cout<<"Elemento "<<elemento<<" nao encontrado\n";
	else cout<<"Elemento "<<elemento<<" encontrado na posicao "<<q<<"\n";

	elemento = 21;
	q = Questao6busca(v, elemento, N);
	if (q<0) cout<<"Elemento "<<elemento<<" nao encontrado\n\n";
	else cout<<"Elemento "<<elemento<<" encontrado na posicao "<<q<<"\n\n";
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 7 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Sobre o algoritmo HeapSort faça o que se pede. {\bf(a)} Reescreva-o em pseudo-código para receber como entrada um vetor $A$ e índices $p<r$ e ordenar o subvetor $A[p,\ldots,r]$. {\bf(b)} Altere-o para utilizar um heap {\bf mínimo} enraizado na última posição do vetor $A$, ao invés de um heap máximo enraizado na primeira posição.

// Usa heap mínimo enraizado na última posição do vetor, considerando o vetor da posição p até a posição r
void min_heapify(vector<int>& v, int i, int p, int r) {
    int m = i;
    int esq = 2*i-r-1;
    int dir = esq-1;
    if ((esq>=p)&&(v[esq]<v[i])) m = esq;
    if ((dir>=p)&&(v[dir]<v[m])) m = dir;
    if (m != i) {
        trocar(v[i], v[m]);
        min_heapify(v,m,p,r);
    }
}

void HeapSort_min(vector<int>& v, int p, int r) {
    int i;
    for (i=(r+p+2)/2; i<=r; i++) {
        min_heapify(v,i,p,r);
    }
    for (i=p;i<r;i++) {
        trocar(v[r], v[i]);
        p = p+1;
        min_heapify(v,r,p,r);
    }
}

void Questao7(int N) {
	vector<int> v(N,0);
	srand(time(NULL));
	cout<<"Vetor original: ";
	for (int i = 0; i<N; i++) {
        v[i] = rand() % 1000;
        cout<<v[i]<<" ";
	}
	cout<<"\n\n";
	cout<<"Vetor ordenado: ";
	HeapSort_min(v,0,N-1);
	for (int i=0; i<N; i++) cout<<v[i]<<" ";
	cout<<"\n\n";
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 9 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Seja $X[1\ldots n]$ um vetor qualquer (os elementos desse vetor não são necessariamente inteiros ou caracteres; podem ser objetos quaisquer, como frutas ou arquivos executáveis). Suponha que você possui apenas um operador ``$=$'' que permite comparar se um objeto é igual a outro. Dizemos que $X$ tem um elemento {\bf majoritário} $x$ se mais da metade de seus elementos são iguais a $x$. Escreva um algoritmo de tempo $\Theta(n\ \log\ n)$ que diz se $X$ possui ou não um elemento majoritário. Caso sim, devolva o seu valor. {\bf Dica:} Se $x$ é majoritário em $X$, então $x$ é majoritário na primeira ou na segunda metade de $X$ (explique porquê).

int Conta(vector<int>& v, int p, int r, int elemento) {
    int cont = 0;
    for (int i=p; i<=r; i++) {
        if (v[i]==elemento) cont++;
    }
    return cont;
}

int Questao9(vector<int>& v, int p, int r) {
    if (p==r) return v[p];
    int q = (p+r)/2;
    int x1 = Questao9(v,p,q);
    int x2 = Questao9(v,q+1,r);

    int N1=-1; int N2=-1;
    if (x1>=0) N1 = Conta(v,p,r,x1);
    if (x2>=0) N2 = Conta(v,p,r,x2);
    if (N1 > (r-p+1)/2) return x1;
    if (N2 > (r-p+1)/2) return x2;
    return -1;
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 10 -------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Sejam $X[1\ldots n]$ e $Y[1\ldots n]$ dois vetores ordenados. Escreva um algoritmo $\Theta(\log\ n)$ para encontrar a mediana de todos os $2n$ elementos nos vetores $X$ e $Y$. Prove esta complexidade.

int Questao10(vector<int>& v1, vector<int>& v2, int p1, int r1, int p2, int r2) {
    if ((r1-p1<=1)&&(r2-p2<=1)) {
        int n = r1-p1+1 + r2-p2+1;
        vector<int> aux(n,0);
        int j=0;
        for (int i=p1; i<=r1; i++) aux[j++] = v1[i];
        for (int i=p2; i<=r2; i++) aux[j++] = v2[i];
        InsertionSort(aux,0,n-1);
        int med = aux[n/2];
        return med;
    }

    int q1 = (p1+r1)/2;
    int q2 = (p2+r2)/2;
    int med1 = v1[q1];
    int med2 = v2[q2];

    if (med1==med2) return med1;
    if (med1<med2)
        return Questao10(v1, v2,q1,r1,p2,q2);
    else
        return Questao10(v1, v2,p1,q1,q2,r2);
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 11 --------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Faça um algoritmo de tempo $\Theta(n\log n)$ para resolver o seguinte problema: dado um vetor com $n$ números inteiros positivos e um outro número inteiro positivo $x$, determine se existem ou não dois elementos cuja soma é igual a $x$.

void Questao11(vector<int>& v, int n, int x) {
    HeapSort(v,0,n-1);
    int i, q=-1;
    for (i=0; i<n; i++) {
        q = Busca_Binaria(v, x-v[i], 0, n-1);
        if (q>=0) break;
    }
    if (q<0) cout<<"<Questao11> NAO existem elementos com soma = "<<x<<endl;
    else cout<<"<Questao11> Existem os elementos: "<<v[i]<<"+"<<v[q]<<" = "<<x<<endl;
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 12 -------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Seja $X[1\ldots n]$ um vetor de inteiros. Dados $i<j$ em $\{1,\ldots,n\}$, dizemos que $(i,j)$ é uma inversão de $X$ se $X[i]>X[j]$. Escreva um algoritmo $\Theta(n\ log\ n)$ que devolva o número de inversões em um vetor $X$. {\bf Dica:} Tenta fazer essa contagem enquanto ordena o vetor no Merge-Sort.

int Merge_cont(vector<int>& v, int p, int q, int r) {
    int infinito = INT_MAX;
    int N1 = q-p+1;
    int N2 = r-q;
    vector<int> esq(N1+1,0);
    vector<int> dir(N2+1,0);
    for (int i=0; i<N1; i++) esq[i]=v[p+i];
    for (int j=0; j<N2; j++) dir[j]=v[q+j+1];
    esq[N1] = infinito;
    dir[N2] = infinito;

    int i=0; int j=0;
    int cont = 0;
    for (int k=p; k<=r; k++) {
        if (esq[i]<=dir[j]) {
            v[k] = esq[i++];
            cont += j;
        } else {
            v[k] = dir[j++];
        }
    }
    return cont;
}

int Questao12(vector<int>& v, int p, int r) {
    if (p>=r) return 0;
    int q = (p+r)/2;
    int cont1 = Questao12(v,p,q);
    int cont2 = Questao12(v,q+1,r);
    int cont3 = Merge_cont(v,p,q,r);
    return cont1 + cont2 + cont3;
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 14 -------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Suponha que você tem $k$ vetores ordenados de tamanho $n$ e deseja combiná-los em um único vetor ordenado de tamanho $kn$. {\bf(a)} Uma ideia é usar o algoritmo {\sc Intercala}, intercalando o primeiro e o segundo, depois intercalando o resultado com o terceiro, depois com o quarto e etc... Qual a complexidade desse procedimento em termos de $k$ e $n$? {\bf(b)} Mostre uma solução mais eficiente usando divisão e conquista.

void Merge(vector<int>& v, int p, int q, int r) {
    int infinito = INT_MAX;
    vector<int> esq;
    vector<int> dir;
    for (int i=p  ; i<=q; i++) esq.push_back(v[i]);
    for (int i=q+1; i<=r; i++) dir.push_back(v[i]);
    esq.push_back(infinito);
    dir.push_back(infinito);

    int i=0;
    int j=0;
    for (int k=p; k<=r; k++) {
        if (esq[i]<=dir[j])
             v[k] = esq[i++];
        else v[k] = dir[j++];
    }
}

void Questao14a(vector<int>& v, int n, int k) {
    for (int i=1; i<k; i++) {
        Merge(v, 0, i*n-1, (i+1)*n-1);
    }
}

void Questao14bb(vector<int>& v, int n, int k) {
    int tam = k*n;
    while (k>1) {
        int i=0;
        while (i+2 <= k) {
            Merge(v, i*n, (i+1)*n-1, min((i+2)*n-1, tam));
            i = i + 2;
        }
        k = ceil(k/2.0);
        n = 2*n;
    }
}

void Questao14b(vector<int>& v, int n, int k1, int k2) {
    if (k2-k1<1) return;

    int k = (k1+k2)/2;
    Questao14b(v,n,k1,k);
    Questao14b(v,n,k+1,k2);

    Merge(v,(k1-1)*n,k*n-1,k2*n-1);
}


// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 16 -------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Seja $X[1\ldots n]$ um vetor de {\bf números reais}. Dizemos que $X$ tem um elemento {\bf popular} $x$ se mais de {\bf um terço} de seus elementos são iguais a $x$. Escreva um algoritmo de tempo linear $\Theta(n)$ que diz se $X$ possui ou não um elemento popular. Caso sim, devolva o seu valor. {\bf Dica:} Use o algoritmo de Seleção do k-ésimo mínimo de tempo linear no pior caso.

int Questao16(vector<int>& v, int N, double prob) {
    int k = ceil(1.0/prob);
    for (int i=1; i<k; i++) {
        int candidato = Selecao(v,0,N-1,i*N/k);
        int cont = Conta(v, 0, N-1, candidato);
        if (cont>prob*N) return candidato;
    }
    return -1;
}

// ------------------------------------------------------------------------------------------------
// ----- QUESTAO 17 -------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
//Dizemos que um algoritmo é de {\bf quase-ordenação} se, para qualquer vetor $A[1\ldots n]$, o algoritmo rearranja os valores do vetor $A$ de modo que $i<j$ implica $A[i]<A[j]+0.1$. Por exemplo, o vetor $A=[1.5\ 1.45\ 2.4\ 2.35\ 3]$ está quase-ordenado. Sabendo que os valores do vetor de entrada são números reais menores que 100, faça um algoritmo de tempo $O(n)$ para quase-ordenar o vetor.

void Questao17(vector<double>& v, int N, int K, double relax) {
    for (int i=0; i<N; i++) v[i] /= relax;
    K /= relax;
    CountingSort(v, N, K);
    for (int i=0; i<N; i++) v[i] *= relax;
}








// ------------------------------------------------------------------------------------------------
// ---- ALGORITMOS AUXILIARES ---------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------


// --- INSERTION_SORT ------------------------
void InsertionSort(vector<int>& v, int p, int r) {
    int i,j,carta;
    for (j=p+1;j<=r;j++) {
        carta = v[j];
        i = j-1;
        while ((i>=p)&&(v[i]>carta)) {
            v[i+1] = v[i];
            i--;
        }
        v[i+1] = carta;
    }
}

// --- HEAP_SORT -------------------------------------
void maxheapify(vector<int>& v, int i, int p, int r) {
    int m = i;
    int esq = p+2*(i-p)+1;
    int dir = p+2*(i-p)+2;
    if ((esq<=r)&&(v[esq]>v[i])) m = esq;
    if ((dir<=r)&&(v[dir]>v[m])) m = dir;
    if (m != i) {
        trocar(v[i], v[m]);
        maxheapify(v,m,p,r);
    }
}

void HeapSort(vector<int>& v, int p, int r) {
    int i;
    for (i=(r+p-1)/2; i>=p; i--) {
        maxheapify(v,i,p,r);
    }
    for (i=r;i>p;i--) {
        trocar(v[p], v[i]);
        r = r-1;
        maxheapify(v,p,p,r);
    }
}

// --- Busca_Binaria --------------------------------------
int Busca_Binaria(vector<int>& v, int elemento, int p, int r) {
    while (p<=r) {
        int q = (p+r)/2;
        if (v[q]< elemento) p = q+1; else
        if (v[q]> elemento) r = q-1; else
        if (v[q]==elemento) return q;
    }
    return -1;
}

// --- Algoritmo PARTICIONE ------------------------
int Particione(vector<int>& v, int p, int r, int pivo) {
    int j, i=p-1;
    for (j=p; j<r; j++) {
        if (v[j] < pivo) {
            i++;
            trocar(v[i], v[j]);
        } else if (v[j]==pivo) {
            trocar(v[j], v[r]);
            break;
        }
    }
    for (j=j; j<r; j++) {
        if (v[j] <= pivo) {
            i++;
            trocar(v[i], v[j]);
        }
    }
    trocar(v[i+1], v[r]);
    return i+1;
}

// --- Algoritmo SELECAO -----------------
int Selecao(vector<int>& v, int p, int r, int k) {
    int i, N=r-p+1;
    if (N<10) {
        if (k>N) k=N;
        InsertionSort(v,p,r);
        return v[p+k-1];
    }
    int tam_M = N/5;
    vector<int> M(tam_M,0);
    for (i=0; i<tam_M; i++) {
        InsertionSort(v, p+5*i, p+5*i+4);
        M[i] = v[p+5*i+2];
    }
    int pivo = Selecao(M, 0, tam_M-1, tam_M/2);
    M.clear();
    int q = Particione(v, p, r, pivo);
    i = q-p+1;
    if (k==i) return v[q];
    if (k<i) return Selecao(v,p,q-1,k);
    return Selecao(v,q+1,r,k-i);
}

// ---- COUNTING-SORT --------------------------------
void CountingSort(vector<double>& A, int N, int K) {
    int i,j;
    vector<double> B(N,0);
    vector<int> C(K+1,0);
    for (j=0; j<N; j++) C[(int)A[j]]++;
    for (i=1; i<=K; i++) C[i] = C[i]+C[i-1];
    for (j=N-1; j>=0; j--) B[--C[(int)A[j]]] = A[j];
    for (j=0; j<N; j++) A[j] = B[j];
}

// --- Imprimir vetor em arquivo ------------------------
void imprimir_vetor(vector<auto>& v, int N, string filename) {
    if (filename=="") filename="saida.txt";
    ofstream arq;
    arq.open(filename.c_str());
    for (int i=0;i<N;i++) arq<<v[i]<<" ";
    arq.close();
}